package kmp;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 */
public class leetCode22_generateParenthesis {
    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        StringBuilder trace = new StringBuilder();
        build(n,n,trace);
        return ans;
    }

    public void build(int left,int right, StringBuilder trace){
        if(right < left) return;
        if(left < 0 || right < 0)return;
        if(left == 0 && right == 0){
            ans.add(trace.toString());
            return;
        }

        trace.append('(');
        build(left - 1, right, trace);
        trace.deleteCharAt(trace.length() - 1);

        trace.append(')');
        build(left, right - 1, trace);
        trace.deleteCharAt(trace.length() - 1);




    }
}
